package com.zhang.topic;

import java.util.HashMap;

/**
 * @title: 剑指 Offer 10- I. 斐波那契数列
 * @author: zhang
 * @date: 2022/4/6 14:24
 */
public class Fibonacci {
    public static void main(String[] args) {

    }

    /**记忆递归*/
    private static HashMap<Integer, Integer> map = new HashMap<>();
    public static int fib1(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int sum1 = (fib1(n - 1) + fib1(n - 2)) % 1000000007;
        map.put(n, sum1);
        return sum1;
    }


    /**动态规划*/
    public static int fib2(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int sum = 0;
        int pre = 1;
        int prePre = 0;
        for (int i = 2; i <= n; i++) {
            sum = (pre+prePre) % 1000000007;
            prePre = pre;
            pre = sum;
        }
        return sum;
    }

}
